package com.lql.algorithm;

/**
 * 分治算法——汉诺塔
 */
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower(5,'A','B','C');
    }

    /**
     * 实现汉诺塔
     *
     * @param num 几个盘
     * @param a   第一个塔
     * @param b   第二个塔
     * @param c   第三个塔
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        if (num == 1) {
            //盘数为1时，直接将a上的盘移动到c盘
            System.out.println(a + "-->" + c);
        } else {
            //num>=2时，递归
            //将最下面的一个盘作为一部份，上面的所有盘作为一部分
            //a塔上的num-1盘个借助c移动到b
            hanoiTower(num - 1, a, c, b);
            System.out.println(a + "-->" + c);
            //将b塔上的盘，借助a塔移动到c塔
            hanoiTower(num - 1, b, a, c);
        }
    }
}
